User blog:B1mb0w/General Proof of Strong D Function Growth Rate
This is the general proof of the Strong D Function growth rate. It will focus on 3 parameter functions of the form D(l,m,n) and the proof will be extended later for larger numbers of parameters. Strong D Functions D(m,n) with 2 Parameters For 2 parameters the Strong D Function is the same as the Deeply Nested Ackermann Function which uses the small d notation. Refer to the Comparison Rule C1 on that blog for the proof of the following: \(d(m,n) >> f_{m-1}(n+2)\) then \(D(4,1) >> f_{3}(3) = f_{\omega}(3)\) \(D(n+1,n+1) >> f_n(n+3) >> f_n(n) = f_{\omega}(n)\) This is the growth rate of the 2 parameter function Strong D Functions D(l,m,n) with 3 Parameters Lets start by comparing \(D(1,0,3)\) to \(f_{\omega}(3)\) \(D(1,0,0) = D(0,D(0,1,1),D(0,1,1)) = D(D(1,1),D(1,1)) = D(4,4) >> f_{\omega}(3)\) \(D(1,0,1) = D(0,D(1,0,0),D(1,0,0)) = D(D(4,4),D(4,4)) >> f_{\omega}(D(4,4))\) \(>> f_{\omega}(f_{\omega}(3)) >> f_{\omega}^2(3)\) \(D(1,0,2) = D(0,D(1,0,1),D(1,0,1)) >> f_{\omega}(D(1,0,1)) >> f_{\omega}(f_{\omega}^2(3)) >> f_{\omega}^3(3)\) First proof: \(D(1,0,n) >> f_{\omega}^4(n)\) \(D(1,0,3) = D(0,D(1,0,2),D(1,0,2)) >> f_{\omega}(D(1,0,2)) >> f_{\omega}(f_{\omega}^3(3)) = f_{\omega}^4(3)\) assume \(D(1,0,n-1) >> f_{\omega}^4(n-1)\) then \(D(1,0,n) = D(0,D(1,0,n-1),D(1,0,n-1)) >> f_{\omega}(D(1,0,n-1)) >> f_{\omega}(f_{\omega}^4(n-1))\) \(= f_{\omega}^4(f_{\omega}(n-1)) >> f_{\omega}^4(n)\) Next calculation - getting to \(\omega+1\) \(D(1,0,n+1) = D(0,D(1,0,n),D(1,0,n)) >> f_{\omega}(D(1,0,n)) >> f_{\omega}(f_{\omega}^4(n)) = f_{\omega}^5(n)\) \(D(1,0,n+p) = D(0,D(1,0,n+p),D(1,0,n+p)) >> f_{\omega}^{p+4}(n)\) \(D(1,0,n+n-4) >> f_{\omega}^{n-4+4}(n) = f_{\omega}^n(n) = f_{\omega+1}(n)\) Second proof: \(D(1,m,0) >> f_{\omega}^m(f_{\omega+1}(m))\) \(D(1,3,0) = D(0,D(1,2,3),D(1,2,3)) >> D(1,0,8) = D(1,0,6+6-4) >> f_{\omega+1}(6)\) \(= f_{\omega}^6(6) = f_{\omega}^3(f_{\omega}^3(6) >> f_{\omega}^3(f_{\omega}^3(3)) = f_{\omega}^3(f_{\omega+1}(3))\) assume \(D(1,m-1,0) >> f_{\omega}^{m-1}(f_{\omega+1}(m-1))\) then \(D(1,m,0) = D(0,D(1,m-1,m),D(1,m-1,m)) >> f_{\omega}(D(1,m-1,m))\) \(>> f_{\omega}(f_{\omega}(D(1,m-1,m-1))\) \(>> f_{\omega}^2(f_{\omega}(D(1,m-1,m-2)) >> f_{\omega}^3(f_{\omega}(D(1,m-1,m-3))\) \(>> f_{\omega}^m(f_{\omega}(D(1,m-1,m-m)) = f_{\omega}^{m+1}(D(1,m-1,0))\) \(>> f_{\omega}^{m+1}(f_{\omega}^{m-1}(f_{\omega+1}(m-1))) = f_{\omega}^{m.2}(f_{\omega}^{m-1}(m-1))\) \(= f_{\omega}^{m.2+m-2}(f_{\omega}(m-1)) >> f_{\omega}^{m.2+m-2}(m) >> f_{\omega}^{m.2-2}(f_{\omega}^m(m))\) \(>> f_{\omega}^m(f_{\omega}^m(m)) = f_{\omega}^m(f_{\omega+1}(m))\) Next calculation - general formula for \(D(1,m,n)\) \(D(1,m,1) = D(D(1,m,0),D(1,m,0)) >> f_{f_{\omega}(D(1,m,0))}(f_{\omega}(D(1,m,0))) = f_{\omega}(D(1,m,0))\) \(>> f_{\omega}(f_{\omega}^m(f_{\omega+1}(m))) = f_{\omega}^{m+1}(f_{\omega+1}(m))\) \(D(1,m,n) >> f_{\omega}^{m+n}(f_{\omega+1}(m))\) Next calculation - general formula for \(D(1,n,n)\) \(D(1,n,n) >> f_{\omega}^{n.2}(f_{\omega+1}(n))\) Next calculation - \(D(2,0,0)\) \(D(2,0,0) = D(1,D(1,2,2),D(1,2,2)) >> f_{\omega}^{D(1,2,2)}(f_{\omega+1}(D(1,2,2)))\) \(>> f_{\omega+1}(D(1,2,2)) >> f_{\omega+1}(f_{\omega}^{2.2}(f_{\omega+1}(2))))\) \(= f_{\omega+1}(f_{\omega}^4(f_{\omega}^2(2))) = f_{\omega+1}(f_{\omega}^5(f_{\omega}(2))))\) \(>> f_{\omega+1}(f_{\omega}^5(5)) = f_{\omega+1}(f_{\omega+1}(5)) = f_{\omega+1}^2(5)\) Third proof: \(D(2,0,n) >> f_{\omega+1}^2(n)\) \(D(2,0,5) >> D(2,0,0) >> f_{\omega+1}^2(5)\) assume \(D(2,0,n-1) >> f_{\omega+1}^2(n-1)\) then \(D(2,0,n) = D(1,D(2,0,n-1),D(2,0,n-1)) >> f_{\omega}^{D(2,0,n-1).2}(f_{\omega+1}(D(2,0,n-1)))\) \(>> f_{\omega+1}(f_{\omega+1}^2(n-1)) = f_{\omega+1}^2(f_{\omega+1}(n-1))\) \(>> f_{\omega+1}^2(n)\) Next calculation - getting to \(\omega+2\) \(D(2,0,n+1) = D(1,D(2,0,n),D(2,0,n)) >> f_{\omega}^{D(2,0,n).2}(f_{\omega+1}(D(2,0,n)))\) \(>> f_{\omega+1}(D(2,0,n))) >> f_{\omega+1}(f_{\omega+1}^2(n))) = f_{\omega+1}^3(n))\) \(D(2,0,n+p) = D(1,D(2,0,n+p),D(2,0,n+p)) >> f_{\omega+1}^{p+2}(n))\) \(D(2,0,n+n-2) >> f_{\omega+1}^{n-2+2}(n) = f_{\omega+2}(n)\) Fourth proof: \(D(2,m,0) >> f_{\omega+1}^m(f_{\omega+2}(m))\) \(D(2,3,0) = D(1,D(2,2,3),D(2,2,3)) >> D(1,D(2,0,8),D(2,0,8))\) \(>> f_{\omega}^{D(2,0,8).2}(f_{\omega+1}(D(2,0,8))) >> f_{\omega+1}(D(2,0,8))\) \(= f_{\omega+1}(D(2,0,5+5-2)) >> f_{\omega+1}(f_{\omega+2}(5))\) \(= f_{\omega+1}(f_{\omega+1}^5(5)) = f_{\omega+1}^3(f_{\omega+1}^3(5)) >> f_{\omega+1}(f_{\omega+1}^3(3))\) \(= f_{\omega+1}^3(f_{\omega+2}(3))\) assume \(D(2,m-1,0) >> f_{\omega+1}^{m-1}(f_{\omega+2}(m-1))\) then \(D(2,m,0) = D(1,D(2,m-1,m),D(2,m-1,m)) >> f_{\omega}^{D(2,m-1,m).2}(f_{\omega+1}(D(2,m-1,m)))\) \(>> f_{\omega+1}(D(2,m-1,m)) >> f_{\omega+1}(f_{\omega+1}(D(2,m-1,m-1))\) \(>> f_{\omega+1}^2(f_{\omega+1}(D(2,m-1,m-2)) >> f_{\omega+1}^3(f_{\omega+1}(D(2,m-1,m-3))\) \(>> f_{\omega+1}^m(f_{\omega+1}(D(2,m-1,m-m)) = f_{\omega+1}^{m+1}(D(2,m-1,0))\) \(>> f_{\omega+1}^{m+1}(f_{\omega+1}^{m-1}(f_{\omega+1}^{m-1}(f_{\omega+2}(m-1))))\) \(>> f_{\omega+1}^{m.2}(f_{\omega+1}^{m-1}(f_{\omega+2}(m-1))) = f_{\omega+1}^{m.3-1}(f_{\omega+1}^{m-1}(m-1))\) \(= f_{\omega+1}^{m.4-3}(f_{\omega+1}(m-1)) >> f_{\omega+1}^{m.4-3}(m) = f_{\omega+1}^{m.3-3}(f_{\omega+1}^m(m))\) \(= f_{\omega+1}^{m.3-3}(f_{\omega+2}(m)) >> f_{\omega+1}^m(f_{\omega+2}(m))\) Next calculation - general formula for \(D(2,m,n)\) \(D(2,m,1) = D(1,D(2,m,0),D(2,m,0)) >> f_{\omega}^{D(2,m,0).2}(f_{\omega+1}(D(2,m,0),)) >> f_{\omega+1}(D(2,m,0))\) \(>> f_{\omega+1}(f_{\omega+1}^m(f_{\omega+2}(m))) = f_{\omega+1}^{m+1}(f_{\omega+2}(m))\) \(D(2,m,n) >> f_{\omega+1}^{m+n}(f_{\omega+2}(m))\) Next calculation - general formula for \(D(2,n,n)\) \(D(2,n,n) >> f_{\omega+1}^{n.2}(f_{\omega+2}(n))\) Fifth proof: \(D(l,0,n) >> f_{\phi}^2(n)\) assume \(D(l-1,0,n) >> f_{\phi-1}^2(n))\) \(D(l-1,m,n) >> f_{\phi-1}^{m+n}(f_{\phi}(m))\) then \(D(l,0,0) = D(l-1,D(l,l-1,l-1),D(l,l-1,l-1)) >> f_{\phi-1}^{D(l,l-1,l-1))+D(l,l-1,l-1))}(f_{\phi}(D(l,l-1,l-1))))\) \(>> f_{\phi}(D(l,l-1,l-1)) >> f_{\phi}(D(l-1,D(l,l-1,l-2),D(l,l-1,l-2)))\) \(>> f_{\phi}(f_{\phi-1}^{D(l,l-1,l-2)+D(l,l-1,l-2)}(f_{\phi}(D(l,l-1,l-2)))))\) \(>> f_{\phi}(f_{\phi-1}(f_{\phi}(D(l,l-1,l-2)))) >> f_{\phi}(f_{\phi}(D(l,l-1,l-2))) >> f_{\phi}^2(D(l,l-1,l-2))\) \(>> f_{\phi}^2(3)\) \(D(l,0,3) >> D(l,0,0) >> f_{\phi}^2(3))\) assume \(D(l,0,n-1) >> f_{\phi}^2(n-1)\) then \(D(l,0,n) = D(l-1,D(l,0,n-1),D(l,0,n-1)) >> f_{\phi-1}^{D(l,0,n-1))+D(l,0,n-1))}(f_{\phi}(D(l,0,n-1))))\) \(>> f_{\phi}(D(l,0,n-1)) >> f_{\phi}(f_{\phi}^2(n-1))\) \(= f_{\phi}^2(f_{\phi}(n-1)) >> f_{\phi}^2(n)\) Sixth proof: \(D(l,m,n) >> f_{\phi}^{m+n}(f_{\phi+1}(m))\) assume \(D(l-1,m,n) >> f_{\phi-1}^{m+n}(f_{\phi}(m))\) \(D(l,0,n) >> f_{\phi}^2(n)\) then \(D(l,3,0) = D(l-1,D(l,2,3),D(l,2,3)) >> f_{\phi-1}^{D(l,2,3).2}(f_{\phi}(D(l,2,3)))\) \(>> f_{\phi}(D((l,2,3)) >> f_{\phi}(D(l-1,D(l,2,2),D(l,2,2)))\) \(>> f_{\phi}(f_{\phi-1}^{D(l,2,2)+D(l,2,2)}(f_{\phi}(D(l,2,2))))\) \(>> f_{\phi}(f_{\phi}(D(l,2,2))) >> f_{\phi}^2(D(l-1,D(l,2,1),D(l,2,1))\) \(>> f_{\phi}^2(D(l,2,1)) >> f_{\phi}^2(f_{\phi}(D(l-1,D(l,2,0),D(l,2,0)))\) \(>> f_{\phi}^3(D(l,2,0)) >> f_{\phi}^3(f_{\phi}(D(l-1,D(l,1,2),D(l,1,2)))\) \(>> f_{\phi}^4(D(l,1,2)) >> f_{\phi}^4(D(l,0,3)) >> f_{\phi}^4(f_{\phi}^2(3)) = f_{\phi}^3(f_{\phi}^3(3))\) \(= f_{\phi}^3(f_{\phi+1}(3))\) assume \(D(l,m-1,0) >> f_{\phi}^m(f_{\phi+1}(m-1))\) then \(D(l,m,n) = D(l-1,D(l,m,n-1),D(l,m,n-1)) >> f_{\phi-1}^{D(l,m,n-1)+D(l,m,n-1)}(f_{\phi}(D(l,m,n-1)))\) \(>> f_{\phi}(D((l,m,n-1)) >> f_{\phi}(D(l-1,D(l,m,n-2),D(l,m,n-2)))\) \(>> f_{\phi}(f_{\phi-1}^{D(l,m,n-2)+D(l,m,n-2)}(f_{\phi}(D(l,m,n-2))))\) \(>> f_{\phi}(f_{\phi}(D(l,m,n-2))) >> f_{\phi}^2(D(l-1,D(l,m,n-3),D(l,m,n-3))\) \(>> f_{\phi}^2(D(l,m,n-3)) >> f_{\phi}^2(f_{\phi}(D(l-1,D(l,m,n-4),D(l,m,n-4)))\) ... \(>> f_{\phi}^{n-1}(D(l,m,n-n)) >> f_{\phi}^{n-1}(D(l,m,0) >> f_{\phi}^{n-1}(f_{\phi}(D(l-1,D(l,m-1,m),D(l,m-1,m)))\) \(>> f_{\phi}^n(D((l,m-1,m)) >> f_{\phi}^n(D(l-1,D(l,m-1,m-1),D(l,m-1,m-1)))\) \(>> f_{\phi}^{n+1}(D((l,m-1,m-1)) >> f_{\phi}^{n+1}(D(l-1,D(l,m-1,m-2),D(l,m-1,m-2)))\) \(>> f_{\phi}^{n+2}(D((l,m-1,m-2)) >> f_{\phi}^{n+1}(D(l-1,D(l,m-1,m-3),D(l,m-1,m-3)))\) ... \(>> f_{\phi}^{n+m}(D((l,m-1,m-m)) >> f_{\phi}^{n+m}(D(l-1,m-1,0)) >> f_{\phi}^{n+m}(f_{\phi}^m(f_{\phi+1}(m-1)))\) \(= f_{\phi}^{n+m.2}(f_{\phi+1}(m-1)) = f_{\phi}^{n+m.2}(f_{\phi}^{m-1}(m-1))\) \(= f_{\phi}^{n+m.3-2}(f_{\phi}(m-1)) >> f_{\phi}^{n+m.3-2}(m) = f_{\phi}^{n+m.2-2}(f_{\phi}^{m}(m))\) \(= f_{\phi}^{n+m.2-2}(f_{\phi+1}(m))\) (outdated) References The following references are likely to be outdated because the above proofs and examples will be more reliable. Please keep this in mind if you refer to any of these blogs. *Strong D Function Calculations **Comparing Fast Growing Hierarchy Functions ***Nested f omega functions Category:Blog posts